C++ Trees
Volume Number: 11
Issue Number: 4
Column Tag: C++ Graphics Class
Homerolled Hierarchies 
C++ objects to manage and draw trees dynamically
By Eric Rosé, cp3a@andrew.cmu.edu
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
In the past thirty years, a considerable amount of research has been done on the
automatic drawing of graphs (that’s the node-and-arc kind - not the Excel kind). Of
special interest to interface designers are algorithms which can be used to display a
special kind of graph: the hierarchical tree. Trees are a natural way to represent
information which can be hierarchically subdivided, such as: organizational charts,
design spaces, directory structures, common data structures like binary search trees,
B-trees, and AVL-trees. In the last ten years or so there have been many papers
which discuss algorithms for aesthetically laying out hierarchical trees (see
references), though few of them are intended to do so dynamically. This article
discusses two strategies for drawing dynamically changing hierarchical trees, and
provides a set of five C++ classes which use these strategies to draw trees while taking
into account several customizable display options.
Since the code is rather sizable, I will only present the class interfaces and
important parts of the method implementations. The source code disk includes not only
the full source code for these classes, but the code for an application which I wrote to
test all of the features of both tree algorithms.
Algorithms
Both of the following algorithms assume that each node in a tree consists of a pointer
back to its parent, a linked list of child nodes, and a block of data which it can compute
the size of. This provides a structure which is very easy to recursively traverse.
Algorithm ER
The first algorithm is a recursive routine which I devised in response to a challenge in
a data structures class. It positions nodes by recursively calculating rectangles which
enclose successively larger subtrees and justifying the parent of the subtree within
that rectangle.
Figure 1. Decomposition of a tree by algorithm ER
ER takes as parameters a node to place, and its desired top left corner. If the node
does not have any children, the node’s top left corner is assigned to be the passed-in
coordinate. If the node does have children, ER calls itself for each child, accumulating
the width of all previous subtrees and adding it to the passed-in coordinate at each call.
This insures that every node will be to the right of the subtrees which come before it.
When all the children have been considered, the algorithm centers the parent over the
children and then exits. A pseudo-code version of ER is shown below.
1 ER (Point topLeft, node NodeToPlace) {
2 Point TL = topLeft
3 if nodeToPlace has children
{
4 TL.v += child/parent margin
5 for each child of NodeToPlace
{
6 ER (TL, child)
7 TL.h += width of child's subtree + sibling margin
}
8 justify NodeToPlace over its children
}
9 else
10 NodeToPlace's top left corner = topLeft
}
Note that if we simply change lines 4 and 7 as shown below, we get a tree which
is oriented horizontally rather than vertically.
4 TL.h += child/parent margin
7 TL.v += height of child's subtree + sibling margin
The trees drawn by algorithm ER are aesthetically pleasing, and good for
displaying trees with fairly evenly sized subtrees. A drawback is that it does not make
any attempts to reduce white space by packing nodes more closely together. For
example, opportunistic compression of the subtree whose root is “Paul” would
produce the subtree shown in Figure 2, which is approximately 75% as wide.
Figure 2. Opportunistic Compression of the sample tree
Algorithm SG
The second algorithm, also recursion-based, is used in a graphics visualization tool
called SAGE, developed at Carnegie Mellon’s robotics institute. It works by making
position estimates which place each node as close as possible to its siblings, and then
calculating their real positions as it comes back out of the recursion. A pseudo-code
version of SG is shown below, followed by an English description.
1 SG (Node NodeToPlace, short level, short levelOffset) {
2 if NodeToPlace's estTopLeft.h is greater than Contour[level]
3 set estTopLeft.h to Contour[level];
4 if NodeToPlace has children
{
5 for each child of NodeToPlace
{
6 estimate the child's topleft position
7 SG (child, level+1, levelOffset);
}
}
8 Justify the node and fix its position
9 Contour[level] = the node's rightmost position
}
Again, note that changing lines 2, 3, and 9 as shown below will effectively change
the orientation of the tree to horizontal instead of vertical.
2 if NodeToPlace's estTopLeft.v is greater than Contour[level]
3 set estTopLeft.v to Contour[level];
9 Contour[level] = the node's bottommost position
Before SG begins, we create an array called Contour with an entry for each level
of the tree. This array is used to store the rightmost position where a node may be
placed; all entries are initialized to zero. SG takes as parameters a node to place, its
level in the tree, and the vertical distance between it and its parent. If the node has
children, then for each child it first estimates the position of the child’s top left
corner and then calls SG on it. Estimates are made in the following way: it places the
first child by taking the cumulative width of all the children, dividing that width in
half, and subtracting it from its estimated center (i.e., its estimated top-left position
plus half its width). Each subsequent child is placed by adding the between-node
margin to the value in the Contour array for that level of the tree.
When SG first considers a node (i.e., on its way into the recursion) it checks the
node’s estimated top-left position against the value in the Contour array. If it is
smaller than the value in the array, it is replaced with the value in the array plus the
between-node margin. This insures that each node is placed as close as possible to its
left sibling. When SG considers the same node on its way out of the recursion, it
revises its estimate of the node’s position by centering it over its children. If it has no
children, the estimate is not revised at all. Having fixed the top left position, SG
updates the value of the Contour array to correspond to the node’s right border. In this
way, SG insures that the node’s right sibling will be placed correctly.
Figure 3 provides a visual walk-through of the way in which SG would operate on
a simple tree. (Gray frames indicate nodes whose positions are estimations. Black
frames indicate nodes whose positions have been fixed.)
Figure 3. Visual trace of algorithm SG
The Creeping Feature Creature
Many of the algorithms which are discussed in the literature have been developed to
address specific instances of the tree drawing problem; ie. top-down binary trees,
trees with fixed-size nodes, etc. When I set about designing the tree-drawing classes,
I decided that it would be useful to build in a lot of flexibility. For example, it would
be nice to be able to change the orientation of a tree from top-down to left-right by
just tweaking a parameter. I finally decided on seven characteristics which should be
dynamically modifiable:
1. size, shape, and data content of nodes in the tree
2. number of children per node
3. justification (left, center, right) of nodes over their children.
4. minimum distance between a node and its siblings
5. minimum distance between a node and its children
6. orientation (top-down, bottom-up, left-to-right, right-to-left) of the tree
7. how lines are drawn between nodes and their children (right-angle,
point-to-point)
Since the point of the exercise is to be able to dynamically modify the tree, here’s
the list of operations we want to support:
1. Add a child
2. Insert a child
3. Insert a parent
4. Delete a child and promote its children
5. Delete a child and all of its children
6. Change the content (and so possibly the size and shape) of a node
As if that wasn’t enough, we will also add the restriction that the only nodes
which should be redrawn when the above operations are performed are the ones whose
contents or positions change. There are two reasons for this. The first is to reduce
unsightly flicker. For those who respond to this reason by saying “use an offscreen
GWorld, dummy”, the second reason is to save time spent doing redraw. While
offscreen GWorlds do reduce flicker, redrawing every node on every operation causes
unpleasant delays if you have a large number of moderately complex nodes (trust me -
I fought this problem all summer long.)
Anybody appalled yet? Relax - everything except the last restriction is pretty
straightforward (though the switch statements do get a bit daunting in places!).
OOP(s)!
“The time has come”, the Walrus said, “to talk of implementation details.” In other
words, given the algorithms we are using and the features we want, how can we
partition everything into classes? One intuitive approach (and, in fact, the one I use)
is to treat both the tree and the nodes within the tree as independent objects. Since
nodes are objects, their data content (and consequently their size and shape) can be